//
// Created by Shao Wenhan on 2021/9/28.
//

#ifndef FINDANDUPDATEMEDIAN_MEDIANOFFIXEDLENGTHARRAY_H
#define FINDANDUPDATEMEDIAN_MEDIANOFFIXEDLENGTHARRAY_H

#include <vector>
#include <algorithm>
using namespace std;

template<typename T>
class MedianOfFixedLengthArray{
private:
    vector<T> m_array;
    int m_mid;
    double getMedianOfEvenEle() const;
    double getMedianOfOddEle() const;
    typedef double(MedianOfFixedLengthArray::*getMedianByParity)() const;
    getMedianByParity m_getMedianByParity;

    int binarySearch(T target) const;
public:
    void initialize(const vector<T> &array);
    double getMedian() const;
    void updateNum(T oldNum, T newNum);
};

template<typename T>
void MedianOfFixedLengthArray<T>::initialize(const vector<T> &array) {
    m_array = array;
    m_mid = (static_cast<int>(array.size()))/2;
    sort(m_array.begin(), m_array.end());
    if(static_cast<int>(array.size())%2)
        m_getMedianByParity = &MedianOfFixedLengthArray<T>::getMedianOfOddEle;
    else
        m_getMedianByParity = &MedianOfFixedLengthArray<T>::getMedianOfEvenEle;
}

template<typename T>
double MedianOfFixedLengthArray<T>::getMedianOfEvenEle() const {
    return static_cast<double>(0.5*(m_array[m_mid-1]+m_array[m_mid]));
}

template<typename T>
double MedianOfFixedLengthArray<T>::getMedianOfOddEle() const {
    return static_cast<double>(m_array[m_mid]);
}

template<typename T>
double MedianOfFixedLengthArray<T>::getMedian() const {
    return (this->*m_getMedianByParity)();
}

template<typename T>
int MedianOfFixedLengthArray<T>::binarySearch(T target) const {
    int left = 0, right = static_cast<int>(m_array.size())-1;
    while(left <= right){
        int mid = (left+right)/2;
        if(m_array[mid] == target)
            return mid;
        else if(m_array[mid] > target)
            right = mid-1;
        else
            left = mid+1;
    }
    return -1;
}

template<typename T>
void MedianOfFixedLengthArray<T>::updateNum(T oldNum, T newNum) {
    int index = binarySearch(oldNum);
    if(newNum > oldNum){
        while(index+1 < m_array.size() and m_array[index+1] < newNum){
            m_array[index] = m_array[index+1];
            index++;
        }
        m_array[index] = newNum;
    }
    else{
        while(index-1 >= 0 and m_array[index-1] > newNum){
            m_array[index] = m_array[index-1];
            index--;
        }
        m_array[index] = newNum;
    }
}

#endif //FINDANDUPDATEMEDIAN_MEDIANOFFIXEDLENGTHARRAY_H
